GATE 2007

Question 1

Consider the following two statements about the function f(x)=|x| 

P. f(x) is continuous for all real values of x
Q. f(x) is differentiable for all real values of x

Which of the following is TRUE?

A
P is true and Q is false.
B
P is false and Q is true.
C
Both P and Q are true.
D
Both P and Q are false.
Engineering-MathematicsCalculus
Question 1 Explanation: 
f(x) = |x|
→ f(x) is continuous for all real values of x

For every value of x, there is corresponding value of f(x).
For x is positive, f(x) is also positive
x is negative, f(x) is positive.
So, f(x) is continuous for all real values of x.
→ f(x) is not differentiable for all real values of x. For x<0, derivative is negative
x>0, derivative is positive.
Here, left derivative and right derivatives are not equal.
Question 2

Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:

A
n and n
B
n2 and n
C
n2 and 0
D
n and 1
Engineering-MathematicsSets-And-Relation
Question 2 Explanation: 
A relation is said to be equivalent relation if it satisfies,
→ Reflexive
→ Symmetric
→ Transitive
Let a set S be,
S = {1, 2, 3}
Now, the smallest relation which is equivalence relation is,
S×S = {(1,1), (2,2), (3,3)}
= 3
= n (for set of n elements)
And, the largest relation which is equivalence relation is,
S×S = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}
= 9
= 32
= n2 (for set of n elements)
Question 3

What is the maximum number of different Boolean functions involving n Boolean variables?

A
n2
B
2n
C
22n
D
2n2
Digital-Logic-DesignBoolean-Algebra
Question 3 Explanation: 
Each “boolean” variable has two possible values i.e 0 and 1.
Number of variables= n
Number of input combinations is 2n.
Each “boolean” function has two possible outputs i.e 0 and 1.
Number of boolean functions possible is 22n.
Formula: The number of m-ary functions possible with n k-ary variables is mkn.
Question 4

Let G be the non-planar graph with the minimum possible number of edges. Then G has

A
9 edges and 5 vertices
B
9 edges and 6 vertices
C
10 edges and 5 vertices
D
10 edges and 6 vertices
Engineering-MathematicsGraph-Theory
Question 4 Explanation: 
Using Euler’s formula we know that,
if n ≥ 3 then e ≤ 3n-6 (for planarity)
where n = no. of vertices
e = no. of edges
Now lets check the options.
A) e=9, n=5
9 ≤ 3(5) - 6
9 ≤ 15 - 6
9 ≤ 9
Yes, it is planar.
B) e=9, n=6
9 ≤ 3(6) - 6
9 ≤ 18 - 6 9 ≤ 12 Yes, it is planar.
iii) e=10, n=5
10 ≤ 3(5) - 6
10 ≤ 15 - 6
10 ≤ 9 No, it is not planar.
So, option C is non-planar graph.
iv) e=10, n=6
10 ≤ 3(6) - 6
10 ≤ 18 - 6
10 ≤ 12
Yes, it is planar.
Question 5

Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?

A
1 2 3 4 5 6
B
1 3 2 4 5 6
C
1 3 2 4 6 5
D
3 2 4 1 6 5
Data-StructuresGraphs
Question 5 Explanation: 
The process to find topological order is,
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.
Question 6

Which of the following problems is undecidable?

A
Membership problem for CFGs.
B
Ambiguity problem for CFGs.
C
Finiteness problem for FSAs.
D
Equivalence problem for FSAs.
Theory-of-ComputationDecidability-and-Undecidability
Question 6 Explanation: 
Whether a given CFG is ambiguous, this problem is undecidable. The reason is there is no algorithm exist for this. Remaining all are decidable.
Question 7

Which of the following is TRUE?

A
Every subset of a regular set is regular.
B
Every finite subset of a non-regular set is regular.
C
The union of two non-regular sets is not regular.
D
Infinite union of finite sets is regular.
Theory-of-ComputationRegular-Language
Question 7 Explanation: 
If a set is finite then it must be regular , as every language which contains finite elements is regular. Hence, every finite subset of a non-regular set is regular.
Every subset of regular set is regular, is false. For example L = {an bn | n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two non-regular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {an bn | n ≥ 0} and its complement Lc = {am bn | m ≠ n } U b*a*.
If we take UNION of L and Lc , we will get ∑*, which is regular. Hence the UNION of two non-regular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.
Question 8

How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates?

A
7
B
8
C
9
D
10
Digital-Logic-DesignDecoder
Question 8 Explanation: 
Each 3-to-8 lines decoder has 8 output lines.
So, we can say that
8 lines covered by ----- 1 decoder
1 line covered by ----- 1/8 decoder
64 lines covered by ----- 64/8 = 8 decoders
8 lines covered by ----- 8/8 = 1 decoder
Hence total no. of decoder needed is,
8 + 1 = 9 decoders.
Question 9

Consider the following Boolean function of four variables:

f(w,x,y,z) = ∑(1,3,4,6,9,11,12,14)

The function is:

A
independent of one variable.
B
independent of two variables.
C
independent of three variables.
D
dependent on all the variables.
Digital-Logic-DesignBoolean-Variables
Question 9 Explanation: 

w and y are not needed to represent the function f. So f is independent of two variables.
Question 10

Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:

A
9, 6, 5
B
7, 7, 6
C
7, 5, 8
D
9, 5, 6
Computer-OrganizationCache
Question 10 Explanation: 
Cache has 128 lines.
Each line size 64 words, so no. of bits for WORD = 6 bits
Because it is 4-way set associative cache, no. of sets in the cache = 128/4 = 32 = 25
No. of bits for the set number = 5
Because the address is 20-bits long, no. of TAG bits = 20-5-6 = 9
Question 11

Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:

A
256 Mbyte, 19 bits
B
256 Mbyte, 28 bits
C
512 Mbyte, 20 bits
D
64 Gbyte, 28 bit
Computer-OrganizationSecondary-Storage
Question 11 Explanation: 
Given that the disk pack has 16 surfaces, 128 tracks per surface, 256 sectors per track and each sector size is 512 bytes.
So the disk pack capacity = 16 * 128 * 256 * 512 bytes = 256 MB
To specify a sector we need the information about surface number, track number and sector number within a track. Surface number needs 4 bits as there are 16 surfaces(24), track number needs 7 bits as there are 128 tracks(27) within a surface, within a track the sector number needs 8 bits as there are 256 sectors (28). Total number bits needed to specify a particular sector = 4+7+8 = 19 bits. Hence option A is the answer.
Question 12

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

A
2h−1
B
2h−1 – 1
C
2h+1– 1
D
2h+1
Data-StructuresBinary-Trees
Question 12 Explanation: 
img src = "https://solutionsadda.in/wp-content/uploads/2020/01/f3-4.jpg">
1, 3, 7, 15, 31, ... = 2h+1 - 1
Question 13

The maximum number of binary trees that can be formed with three unlabeled nodes is:

A
1
B
5
C
4
D
3
Data-StructuresBinary-Trees
Question 13 Explanation: 
Total number of binary trees possible for n nodes is C(n) = (2n)!/(n+1)!n! C(n) = (2(3))!/(3+1)!3! = 6×5×4×3×2×1/4×3×2×1×3×2 = 5
Total no. of possible trees is 5.

Total = 5
Question 14

Which of the following sorting algorithms has the lowest worst-case complexity?

A
Merge sort
B
Bubble Sort
C
Quick Sort
D
Selection Sort
AlgorithmsTime-Complexity
Question 14 Explanation: 
Worst case time complexities are
Merge sort→ O(nlogn)
Bubble sort→ O(n2)
Quick sort→ O(n2)
Selection sort→ O(n2)
Question 15

Consider the following segment of C-code:

  int j, n;
  j = 1;
  while (j <= n)
        j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.

A
⌈log2n⌉ + 1
B
n
C
⌈log2n⌉
D
⌊log2n⌋ + 1
AlgorithmsTime-Complexity
Question 15 Explanation: 
Let us consider n=6, then
1<=6 (✔️)
2<=6 (✔️)
4<=6 (✔️)
8<=6 (❌)
4 comparisons required
Option A:
[log n]+1
[log 6]+1
3+1 = 4 (✔)
Option B:
n=6 (❌)
Option C:
[log n]
[log 6]=3 (❌)
Option D:
[log2n]+1
[log26]+1 = 2+1 = 3 (❌)
Question 16

Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.

     Group I                          Group II
(P) Gang Scheduling              (1) Guaranteed Scheduling
(Q) Rate Monotonic Scheduling    (2) Real-time Scheduling
(R) Fair Share Scheduling        (3) Thread Scheduling
A
P – 3 Q – 2 R – 1
B
P – 1 Q – 2 R – 3
C
P – 2 Q – 3 R – 1
D
P – 1 Q – 3 R – 2
Operating-SystemsMatch-the-Following
Question 16 Explanation: 
⇒ Gang scheduling is used for parallel system that schedules the threads.
⇒ Rate monotonic scheduling is used in Real-time operating system.
⇒ Fair share scheduling distributes the CPU equally among users due to which it generates scheduling process.
Question 17

Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?

A
Context switch time is longer for kernel level threads than for user level threads.
B
User level threads do not need any hardware support.
C
Related kernel level threads can be scheduled on different processors in a multi-processor system.
D
Blocking one kernel level thread blocks all related threads.
Operating-SystemsThreads
Question 17 Explanation: 
A) True, because as kernel level threads are managed by OS and kernel maintains lots of data structure.
B) True, because kernel is not involved in it.
C) True
D) Blocking one kernel level thread blocks all related threads is false, because kernel level threads are independent.
Question 18

Which one of the following is a top-down parser?

A
Recursive descent parser.
B
Operator precedence parser.
C
An LR(k) parser.
D
An LALR(k) parser.
Compiler-DesignParsers
Question 18 Explanation: 
Recursive descent parser is top down parser, while others are bottom up parser.
Question 19

In Ethernet when Manchester encoding is used, the bit rate is:

A
Half the baud rate.
B
Twice the baud rate.
C
Same as the baud rate.
D
None of the above.
Computer-NetworksEthernet
Question 19 Explanation: 
Bit rate is half the baud rate in Manchester encoding as bits are transferred only during a positive transition of the clock.
Question 20

Which one of the following uses UDP as the transport protocol?

A
HTTP
B
Telnet
C
DNS
D
SMTP
Computer-NetworksTransport-layer-Protocol
Question 20 Explanation: 
DNS uses the UDP at the transport layer with port number 53 for name resolution.
HTTP, Telnet and SMTP uses TCP.
Question 21

How many different non-isomorphic Abelian groups of order 4 are there?

A
2
B
3
C
4
D
5
Engineering-MathematicsSets-And-Relation
Question 21 Explanation: 
In this problem first of all we find the exponents of prime nos. that can be taken out from given number.
4 = 22
So, prime no. is 2 and power of 2 is 2. So exponent value 2 is considered now.
Now the no. of ways we can divide 2 into sets will be the answer.
So division can be done as,
{1,1}, {0,2}
in two ways. Hence, answer is 2.
There are 21 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access